package org.gzc.tree;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @Description: 平衡二叉树的实现（待实现）
 * @Author: guozongchao
 * @Date: 2020/8/17 22:51
 */
public class AVLTree {
    private Node root;

    class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }

        public int getHeight() {
            return Math.max(this.left == null ? 0 : this.left.getHeight() , this.right == null ? 0 : this.right.getHeight())+1;
        }

        public void inOrder() {
            if (this.left != null) {
                this.left.inOrder();
            }
            System.out.print(" " + this.value + " ");
            if (this.right != null) {
                this.right.inOrder();
            }
        }
    }

    /**
     * 根据无序数组 创建二叉排序树
     *
     * @param array
     */
    public Node createAVL(int[] array) {
        for (int i = 0; i < array.length; i++) {
            root = insert(root, array[i]);
        }
        return this.root;
    }

    /**
     * 插入一个值到二叉排序树中(递归)
     *
     * @param node  要插入的树的根结点
     * @param value 要插入的值
     */
    public Node insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }
        if(value <node.value){
            node.left = insert(node.left, value);
        }else {
            node.right = insert(node.right, value);
        }

        //每成功插入一个结点，就从该结点往上回溯，寻找第一个出现不平衡的子树结点，对该结点进行调整
        node = adjustBalance(node);

        return node;
    }

    /**
     * 调整二叉排序树达到平衡
     * @param node
     * @return  返回调整后的平衡子树根结点
     */
    private Node adjustBalance(Node node) {
        int bf = getBalanceFactor(node);  //获取当前子树的根结点的平衡因子
        if(Math.abs(bf)<=1){  //当前子树已经是平衡二叉树，直接返回，不进行操作
            return node;
        }
        //否则（不是平衡树），进行旋转操作

        /**
         * bf>0 && |bf| >1  说明当前子树的左子树 高于 右子树，并且高度差大于1
         */
        if(bf>0 && Math.abs(bf)>1){
            /**
             *  获取当前子树的 左子树的平衡因子 leftBF
             *  判断当前子树的 左子树 的 右子树 高度是否比对应的左子树 高
             *  如果是，则需要对 当前子树的 左子树 进行左旋转 ，然后再 对当前子树 进行右旋转
             *  如果不是，则直接 对当前子树 进行 右旋转
             */
            int leftBF = getBalanceFactor(node.left);
            if(leftBF>0){   //当前子树的 左子树 的 右子树 高度是否比对应的左子树 高
                node.left = leftRotate(node.left);  //左旋转
                node = rightRotate(node); //右旋转
            }else{
                node = rightRotate(node);
            }
        }

        /**
         * bf<0 && |bf| >1  说明当前子树的左子树 低于 右子树，并且高度差大于1
         */
        if(bf<0 && Math.abs(bf)>1){
            /**
             *  获取当前子树的 右子树的平衡因子rightBF
             *  判断当前子树的 右子树 的 左子树 高度是否比对应的右子树 高
             *  如果是，则需要对 当前子树的 右子树 进行右旋转 ，然后再 对当前子树 进行左旋转
             *  如果不是，则直接 对当前子树 进行 左旋转
             */
            int rightBF = getBalanceFactor(node.right);
            if(rightBF>0){   //当前子树的 右子树 的 左子树 高度是否比对应的右子树 高
                node.right = rightRotate(node.right);  //右旋转
                node = leftRotate(node); //左旋转
            }else{
                node = leftRotate(node);
            }
        }

        return node;
    }

    /**
     * 获取当前结点的平衡因子
     * 平衡因子 = 左子树高度 - 右子树高度
     * @param node
     * @return
     */
    public int getBalanceFactor(Node node) {
        int leftHeight = node.left == null ? 0 : node.left.getHeight();
        int rightHeight = node.right == null ? 0 : node.right.getHeight();
        return leftHeight - rightHeight;
    }

    /**
     * 对 当前子树进左旋转
     * @param node 子树的根结点
     * @return  返回旋转后 子树的根结点
     */
    private Node leftRotate(Node node) {
        Node newRoot=node.right;  //当前结点node的右子树根结点作为左旋转后的树根，临时保存
        node.right=newRoot.left;  //newRoot的左子树链接到 当前结点node的 右边，作为其右子树
        newRoot.left=node;     //将当前结点node 链接到 新的根结点 的左边，作为其左子树
        return newRoot;
    }

    /**
     * 对 当前子树进行右旋转
     * @param node 子树的根结点
     * @return  返回旋转后 子树的根结点
     */
    private Node rightRotate(Node node) {
        Node newRoot=node.left;  //当前结点node的左子树根结点作为右旋转后的树根，临时保存
        node.left=newRoot.right;  //newRoot的右子树链接到 当前结点node的 左边，作为其左子树
        newRoot.right=node;     //将当前结点node 链接到 新的根结点 的右边，作为其右子树
        return newRoot;
    }



    //中序遍历
    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        root.inOrder();
    }


    public static void main(String[] args) {
        int[] array = new int[]{15,7, 21, 9, 6, 43, 10, 18, 20, 11, 19, 13, 56, 16, 12};
        System.out.println("原始数组：" + Arrays.toString(array));
        AVLTree bst = new AVLTree();
        Node bstRoot = bst.createAVL(array);
        System.out.print("二叉排序树中序遍历：");
        bst.inOrder(bstRoot);
        System.out.println("\n树的高度为：" + bstRoot.getHeight());
        System.out.println("根结点为：" + bstRoot.value);
        System.out.println("根结点的左子树高度为：" + bstRoot.left.getHeight());
        System.out.println("根结点的右子树高度为：" + bstRoot.right.getHeight());

        System.out.println("根结点的平衡因子为：" + bst.getBalanceFactor(bstRoot));

    }

}
